package cn.zhl.map.hash;

import cn.zhl.map.Map;
import cn.zhl.map.visitor.Visitor;
import cn.zhl.tree.BinaryTree;

/**
 * @program: demos
 * @description:
 * @author: 刘振华
 * @create: 2020-05-19 11:18
 **/
public class HashMap<K,V> implements Map<K,V> {
	private int size;
	private static final boolean RED = false;
	private static final boolean BLACK = true;
	private Node<K,V>[] table;
	private static final int DEFAULT_CAPICITY = 1 << 4;
	public HashMap(){
		table = new Node[DEFAULT_CAPICITY];
	}
	@Override
	public int size() {
		return size;
	}

	@Override
	public boolean isEmpty() {
		return size == 0;
	}

	@Override
	public void clear() {
		if(size==0){
			return;
		}
		for(int i = 0 ; i < table.length ; i++){
			table[i] = null;
		}
		size = 0;
	}

	/**
	* @Description:插入节点，返回替代的节点，如果没有返回null
	* @Param:
	* @return:
	* @Author: 刘振华
	* @Date: 2020/5/19 12:15
	*/
	@Override
	public V put(K key, V value) {
		//首先需要根据key计算索引，根据索引添加到对应的node上，然后根据equals判定是否相等
		int index = index(key);
		Node<K, V> root = table[index];
		if(root == null){
			table[index] = new Node<>(key,value,null);
			size++;
		}else{

		}
		return null;
	}

	@Override
	public V remove(K key) {
		return null;
	}

	@Override
	public boolean containsKey(K key) {
		return false;
	}

	@Override
	public boolean containsValue(V value) {
		return false;
	}

	@Override
	public void traversal(Visitor<K, V> visitor) {

	}
	/**
	* @Description:根据key生成索引
	* @Param: 键
	* @return: 索引
	* @Author: 刘振华
	* @Date: 2020/5/19 11:57
	*/
	private int index(K key){
		if(key == null){
			return 0;
		}
		int hash = key.hashCode();
		return (hash ^ (hash >>> 16)) & (table.length - 1);
	}
	protected class Node<K,V> {
		public boolean color;
		public K key;
		public V value;
		public Node<K,V> left;
		public Node<K,V> right;
		public Node<K,V> parent;

		public Node(K key,V value, Node<K,V> parent) {
			this.key = key;
			this.value = value;
			this.parent = parent;
		}

		public boolean isLeaf() {
			return left == null && right == null;
		}

		public boolean hasTwoChildren(){
			return left != null && right != null;
		}

		public boolean isLeftChild(){
			return parent != null && this == parent.left;
		}
		public boolean isRightChild(){
			return parent != null && this == parent.right;
		}

		public Node sibling(){
			if(isLeftChild()){
				return parent.right;
			}
			if(isRightChild()){
				return parent.left;
			}
			return null;
		}
		public Node uncle(){
			if(parent == null){
				return null;
			}
			return parent.sibling();
		}
	}
}
